ABC103 D - Islands War
https://atcoder.jp/contests/abc103/tasks/abc103_d
提出
code: python
n, m = map(int, input().split())
ab = sorted(list(map(int, input().split())) for _ in range(m))
# s,s,s,s,s
ans = 0
# 端と端
解答
code: python
n, m = map(int, input().split())
ab = list(map(int, input().split())) for _ in range(m)
# 1 2 3 4 5 6 7 8 9
# o o
# o o
# 1 2 3 4 5 6 7 8 9
# o o
# o o
# o o
# o o
# o o
ab.sort(key = lambda x:x1)
# print(ab)
# 1, 4], [2, 5 -> 1
# 3, 5], 4, 6, 2, 7, 1, 8, [7, 9 -> 2 7, 9までは4を壊せば遮断できる tmpは必ず増加していく
ans = 1
# bi番目の島の左にかかる橋を壊すとして、tmp変数に壊した橋の位置を記憶
tmp = ab01 - 1
for a, b in ab:
# tmpより右の位置がaだった場合は、新たに橋を壊す必要がある
# biについてソート済みなのでtmpとaを比較すれば必要性を判断することができる
if tmp < a:
ans += 1
tmp = b - 1
print(ans)
テーマ
蟻本 2-2 区間スケジューリング問題
メモ
【AtCoder版！蟻本】ABC103 D - Islands War【区間スケジューリング】
提出
code: python
n, m = map(int, input().split())
ab = list(map(int, input().split())) for _ in range(m)
# 1 2 3 4 5 6 7 8 9
# o o
# o o
# 1 2 3 4 5 6 7 8 9
# o o
# o o
# o o
# o o
# o o
ab.sort()
tmpmin, tmpmax = ab0
ab.pop(0)
ans = 0
for a, b in ab:
if a > tmpmin:
tmpmin = a
if b < tmpmax:
tmpmax = b